Search Results

Documents authored by Plank, Andreas

Document
Short Paper
DOI: 10.4230/LIPIcs.CP.2023.49
Enumerative Level-2 Solution Counting for Quantified Boolean Formulas (Short Paper)

Authors: Andreas Plank, Sibylle Möhle, and Martina Seidl

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
We lift the problem of enumerative solution counting to quantified Boolean formulas (QBFs) at the second level. In contrast to the well-explored model counting problem for SAT (#SAT), where models are simply assignments to the Boolean variables of a formula, we are now dealing with tree (counter-)models reflecting the dependencies between the variables of the first and the second quantifier block. It turns out that enumerative counting on the second level does not give the complete model count. We present the - to the best of our knowledge - first approach of counting tree (counter-)models together with a counting tool that exploits state-of-the-art QBF technology. We provide several kinds of benchmarks for testing our implementation and illustrate in several case studies that solution counting provides valuable insights into QBF encodings.
Cite as

Andreas Plank, Sibylle Möhle, and Martina Seidl. Enumerative Level-2 Solution Counting for Quantified Boolean Formulas (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 49:1-49:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{plank_et_al:LIPIcs.CP.2023.49,
  author =	{Plank, Andreas and M\"{o}hle, Sibylle and Seidl, Martina},
  title =	{{Enumerative Level-2 Solution Counting for Quantified Boolean Formulas}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{49:1--49:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.49},
  URN =		{urn:nbn:de:0030-drops-190867},
  doi =		{10.4230/LIPIcs.CP.2023.49},
  annote =	{Keywords: QBF, Second-Level Model Counting}
}
Document
DOI: 10.4230/LIPIcs.SAT.2023.20
QMusExt: A Minimal (Un)satisfiable Core Extractor for Quantified Boolean Formulas

Authors: Andreas Plank and Martina Seidl

Published in: LIPIcs, Volume 271, 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)

Abstract
In this paper, we present QMusExt, a tool for the extraction of minimal unsatisfiable sets (MUS) from quantified Boolean formulas (QBFs) in prenex conjunctive normal form (PCNF). Our tool generalizes an efficient algorithm for MUS extraction from propositional formulas that analyses and rewrites resolution proofs generated by SAT solvers. In addition to extracting unsatisfiable cores from false formulas in PCNF, we apply QMusExt also to obtain satisfiable cores from Q-resolution proofs of true formulas in prenex disjunctive normal form (PDNF).
Cite as

Andreas Plank and Martina Seidl. QMusExt: A Minimal (Un)satisfiable Core Extractor for Quantified Boolean Formulas. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 271, pp. 20:1-20:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{plank_et_al:LIPIcs.SAT.2023.20,
  author =	{Plank, Andreas and Seidl, Martina},
  title =	{{QMusExt: A Minimal (Un)satisfiable Core Extractor for Quantified Boolean Formulas}},
  booktitle =	{26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)},
  pages =	{20:1--20:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-286-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{271},
  editor =	{Mahajan, Meena and Slivovsky, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2023.20},
  URN =		{urn:nbn:de:0030-drops-184824},
  doi =		{10.4230/LIPIcs.SAT.2023.20},
  annote =	{Keywords: Minimal Unsatisfiable Core, Quantified Boolean Formula}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact